%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "symbol.h"
#include "table.h"
#include "mixalSymbol.h"
#include "simulator.h"
#include "alu.h"

int yylex(void);

int yyerror(char* errormsg) {
	printf("%s\n", errormsg);
}

int isOp = 0; // used to change action in the lex
extern int yylineno; // trace the line number
// to indicate whether an semantic error has occurred in the yacc
extern int hasError;
// the pointer to the initial instruction
extern int entry;

typedef struct constantList constantList;
struct constantList {
	int constant; // the constant defined by the CON directive
	int ip; // the pointer to the instruction which uses literal constant 
	constantList *next; // to form the linked list
};

typedef struct patchList patchList;
struct patchList {
	int ip; // the pointer to the instruction which uses undefined symbol 
	patchList *next; // to form the linked list
};

// mapping from the most recent 'iH' to corresponding value
static int localSymbolMap[10];
// mapping from the local symbol 'iH' to corresponding patch
static patchList* localSymbolPatches[10] = {NULL};
// mapping from the global symbol to corresponding value
static table* globalSymbolMap = NULL;
// mapping from the global symbol to corresponding patch
static table* globalSymbolPatches = NULL;
// the linked list about the literal constant
static constantList *conList = NULL;

// Both the value mapped in the map and the constant in the linked list
// represent the word in the mixal. 

extern int memory[MEM_SIZE]; // used to simulate the memory
static int pc = 0; // the pointer to the next instruction assembled 

static int defaultField = 0; // used for nonterminal 'field'
// indicate whether the expression contains computation
static int hasArith = 0; // only used for address :=> exp
// indicate a symbol referenced in the expression or atom
static mixalSymbol refSym;

static void prolog() {
	// initialize some global variable
	memset(localSymbolMap, 0xff, sizeof(localSymbolMap));
	globalSymbolMap = T_empty();
	globalSymbolPatches = T_empty();
}

static int look(mixalSymbol sym) {
	int ret = -1;
	if(sym.kind == Local) {
		if(sym.local < 0) {
			ret = localSymbolMap[sym.local + 10];
			if(ret == -1) {
				hasError = 1;
				printf("%d: can not find the nearest %dH from backward\n", yylineno, sym.local + 10);
			}
		}
		else if(sym.local < 10) {
			hasError = 1;
			printf("%d: can not use %dH in the expression\n", yylineno, sym.local);
		}
	}
	else if(T_count(globalSymbolMap, sym.global)) 
		ret = (long long)T_look(globalSymbolMap, sym.global);
	return ret;
}

static void installPatch(mixalSymbol sym) {
	// construct a patch and associate that with specified 'sym'
	if(sym.kind == Local) {
		int digit = sym.local;
		if(digit < 0) {
			hasError = 1;
			printf("%d: %dB is not a undefind symbol\n", yylineno, digit + 10);
		}
		else if(digit < 10) {
			hasError = 1;
			printf("%d: %dH is not a undefind symbol\n", yylineno, digit);
		}
		else {
			digit -= 10;
			patchList *p = (patchList*)malloc(sizeof(*p));
			p->next = localSymbolPatches[digit];
			p->ip = pc;
			localSymbolPatches[digit] = p; 
		}
	}
	else {
		patchList *p = (patchList*)malloc(sizeof(*p));
		p->next = T_look(globalSymbolPatches, sym.global);
		p->ip = pc;
		T_insert(globalSymbolPatches, sym.global, p);
	}
}

static void uninstallPatch(patchList *list, int data) {
	// write back 'data' into the address field of instruction
	if(!list)
		return;
	if(list->ip >= 0 && list->ip < MEM_SIZE)
		memory[list->ip] = store(memory[list->ip], 2, data);
	uninstallPatch(list->next, data);
	free(list);
}

static void define(mixalSymbol sym, int data) {
	// associate 'sym' with 'data'
	// if 'sym' has been referenced as a undefind symbol, then uninstall 
	// corresponding patch list.
	if(sym.kind == Local) {
		int digit = sym.local;
		if(digit < 0) {
			hasError = 1;
			printf("%d: %dB can not be defined\n", yylineno, digit + 10);
		}
		else if(digit >= 10) {
			hasError = 1;
			printf("%d: %dF can not be defined\n", yylineno, digit - 10);
		}
		else {
			localSymbolMap[digit] = data;
			uninstallPatch(localSymbolPatches[digit], data);
			localSymbolPatches[digit] = NULL;
		}
	}
	else if(T_count(globalSymbolMap, sym.global)) {
		hasError = 1;
		printf("%d: %s can not be defined more then once\n", yylineno, S_name(sym.global));
	}
	else {
		T_insert(globalSymbolMap, sym.global, (void*)(long long)data);
		uninstallPatch(T_look(globalSymbolPatches, sym.global), data);
		T_insert(globalSymbolPatches, sym.global, NULL);
	}
}

static void installConstantPatch(int constant) {
	// Construct a patch which contains the 'constant' defined by literal 
	// constant and the pointer to the instruction referencing that.
	// And then insert the patch created into the linked list.
	constantList *p = (constantList*)malloc(sizeof(*p));
	p->constant = constant;
	p->ip = pc;
	p->next = conList;
	conList = p;
}

static void assemble(int data) {
	// write memory[pc] with 'data' and increment pc
	if(pc >= 0 && pc < MEM_SIZE) 
		memory[pc++] = data;	
	else {
		hasError = 1;
		printf("memory overflow\n");
	}
}

static void uninstallConstantPatch() {
	// iterate the 'conList', write back 'pc' into the address field of the 
	// instruction referencing literal constant and store the constant at 'pc'
	constantList *p = conList, *q;
	while(p) {
		q = p->next;
		if(p->ip >= 0 && p->ip < MEM_SIZE)
			memory[p->ip] = store(memory[p->ip], 2, pc);
		assemble(p->constant);
		free(p);
		p = q;
	}
	conList = NULL;
}

static void handleSymbol(patchList *list, int data) {
	if(!list)
		return;
	patchList *p = list, *q;
	while(p) {
		q = p->next;
		if(p->ip >= 0 && p->ip < MEM_SIZE)
			memory[p->ip] = store(memory[p->ip], 2, pc);
		free(p);
		p = q;
	} 
	assemble(data);
}

static void handleEndSymbol(patchList *list) {
	// handle the symbol which is defined by the 'END' directive.
	handleSymbol(list, pc);
}

static void handleUndefSymbol(patchList *list) {
	// handle the symbol which is still undefined when scanning the 'END' except
	// the symbol which would be defined by the 'END' directive later.
	// assemble zero before the 'END' and write back the address field of the 
	// instructions referencing that
	handleSymbol(list, 0);
}

static void epilog() {
	// assemble all the literal constants into the memory and write back the
	// address field of the instructions referencing them
	uninstallConstantPatch();
	// handle all the symbols which are still undefined when scanning the 'END'
	// except the symbol which will be defined by the 'END' directive later.
	for(int i = 0; i < 10; ++i) {
		handleUndefSymbol(localSymbolPatches[i]);
		localSymbolPatches[i] = NULL;
	}
	T_dump(globalSymbolPatches, (void(*)(void*))handleUndefSymbol);
	// clear the hash tables
	T_clear(globalSymbolMap);
	T_clear(globalSymbolPatches);
	S_clear();
	globalSymbolMap = NULL;
	globalSymbolPatches = NULL;
}

%}

%union {
	struct {
		int code; // code of operation
		int field; 	// default field of operation
	} op;
	int num;
	mixalSymbol sym;
	char* str; // only for ALF	
}

%token <op> OP
%token <num> NUM
%token <sym> SYMBOL
%token <str> STRING

%token
	ORIG EQU COMMA LPAREN RPAREN
	COLON EQ CON ALF PLUS MINUS STAR DIV SEDIV END

%type <num> address varaddress field word normalInstWithoutLabel exp atom

%start program
%%

program: {prolog();} normalInstList endInst
       ;

exp: atom {$$ = $1;}
   | PLUS atom {$$ = $2; hasArith = 1;}
   | MINUS atom {
       if($2 == -1)
         $$ = -1;
       else
         $$ = neg($2);
       hasArith = 1;
   }
   | exp PLUS atom {
       hasArith = 1;
       if($1 == -1 || $3 == -1)
         $$ = -1;
       else
         $$ = add($1, $3);
   }
   | exp MINUS atom {
       hasArith = 1;
       if($1 == -1 || $3 == -1)
         $$ = -1;
       else
         $$ = sub($1, $3);
   }
   | exp STAR atom {
       hasArith = 1;
       if($1 == -1 || $3 == -1)
         $$ = -1;
       else
         $$ = imul($1, $3);
   }
   | exp DIV atom {
       hasArith = 1;
       if($1 == -1 || $3 == -1)
         $$ = -1;
       else 
         printf("%x / %x = %x\n", $1, $3, $$);
   }
   | exp SEDIV atom {
       hasArith = 1;
       if($1 == -1 || $3 == -1)
         $$ = -1;
       else {
         // We consider -1 as the illegal value to identify whether the 
         // expression has referenced a undefined symbol.
         // However, the return value of idiv(...) maybe -1, which would 
         // interfere our adjustment.
         // Therefore, I have to call clr(...) to clear the overflow bit to
         // make sure that the value of expression would never be -1 when
         // all the symbols referenced in the expression has been defined.
         $$ = clr(idiv($1, 0, $3) >> 32);
       }
   }
   | exp COLON atom {
       hasArith = 1;
       if($1 == -1 || $3 == -1)
         $$= -1;
       else {
         $$ = imul($1, 8); // L * 8
         $$ = add($$, $3); // L * 8 + R
       }
   }
   ;

atom: NUM {$$ = abso($1);}
    | SYMBOL {$$ = look($1); refSym = $1;}
    | STAR {$$ = pc;}
    ;

address: exp {
         if($1 == -1) {
           // the expression has referenced a undefined symbol 
           if(!hasArith) {
             // the expression only consists of a undefined symbol
             // install patch on the undefined symbol
             installPatch(refSym);
             $$ = 0;
           }
           else 
             $$ = -1;
         }
         // clear the flag about whether the expression contains 
         // computation 
         hasArith = 0;
       }
       | constant {$$ = 0;}
       | {$$ = 0;}
       ;

varaddress: COMMA exp {$$ = $2; hasArith = 0;}
          | {$$ = 0;}
          ;

field: LPAREN exp RPAREN {$$ = $2; hasArith = 0;}
     | {$$ = defaultField;}
     ;

word: exp {defaultField = 5;} field {
        if($1 == -1 || $3 == -1)
          $$ = -1;
        else
          $$ = store(0, $3, $1); 
      }
    | word COMMA exp {defaultField = 5;} field {
        if($1 == -1 || $3 == -1 || $5 == -1)
          $$ = -1;
        else
          $$ = store($1, $5, $3);
      }
    ;

constant: EQ word EQ {
            if($2 == -1) {
              hasError = 1;
              printf("%d: literal constant can not be defined with illegal word\n", yylineno);
            }
            else 
              installConstantPatch($2);
            hasArith = 0;
          }
        ;

normalInstWithoutLabel: OP {isOp = 1;} address varaddress 
                        {defaultField = $1.field;} field {
                          $$ = pc;
                          int errorFlag = 0;
                          int data = 0;
                          if($3 == -1) {
                            hasError = 1;
                            errorFlag = 1;
                            printf("%d: illegal address\n", yylineno);
                          }
                          if($4 == -1) {
                            hasError = 1;
                            errorFlag = 1;
                            printf("%d: illegal variable address\n", yylineno);
                          }
                          if($6 == -1) {
                            hasError = 1;
                            errorFlag = 1;
                            printf("%d: illegal field\n", yylineno);
                          }
                          if(!errorFlag) {
                            data = store(0, 45, $1.code); // ~~~~C
                            data = store(data, 36, $6); // ~~~FC
                            data = store(data, 27, $4); // ~~IFC
                            data = store(data, 2, $3); // +AAIFC
                          }
                          assemble(data);
                        }
                      | EQU {isOp = 1;} word {
                          if($3 == -1) {
                            hasError = 1;
                            printf("%d: illegal EQU constant\n", yylineno);
                            $$ = -1; // make the error flood
                          }
                          else
                            $$ = $3;
                          hasArith = 0;
                        }
                      | ORIG {isOp = 1;} word {
                          $$ = pc;
                          if($3 == -1) {
                            hasError = 1;
                            printf("%d: illegal ORIG PC\n", yylineno);
                          }
                          else
                            pc = clr($3); // to make -0 become +0
                          hasArith = 0;
                        }
                      | CON {isOp = 1;} word {
                          $$ = pc;
                          if($3 == -1) {
                            hasError = 1;
                            printf("%d: illegal CON data\n", yylineno);
                            assemble(0);
                          }
                          else
                            assemble($3);
                          hasArith = 0;
                        }
                      | ALF {isOp = 1;} STRING {
                          $$ = pc;
                          char buf[6] = {' ', ' ', ' ', ' ', ' ', '\0'};
                          int len = strlen($3);
                          if(len < 5) 
                            sprintf(buf + 5 - len, "%s", $3);
                          else
                            sprintf(buf, "%.5s", $3);
                          int data = 0;
                          for(int i = 5; i > 0; --i) 
                            data = store(data, i * 9, buf[i - 1] - ' ');
                          assemble(data);
                          free($3);
                        }
                      ;

normalInstWithLabel: SYMBOL normalInstWithoutLabel {
                       if($2 == -1) {
                         hasError = 1;
                         printf("%d: symbol can not be defined with illegal value\n", yylineno);
                       }
                       else
                         define($1, $2);
                     }
                   ;

normalInst: normalInstWithLabel '\n'
          | normalInstWithoutLabel '\n'
          ;
 
endInst1: END word {
            if($2 == -1) {
              hasError = 1;
              printf("%d: illegal entry address\n", yylineno);
            }
            else
              entry = clr($2); // make -0 become +0
            hasArith = 0;
          }
        ;


endInst: SYMBOL endInst1 {
           patchList *list = NULL;
           if($1.kind == Local) {
             int digit = $1.local;
             if(digit < 0) {
               hasError = 1;
               printf("%d: %dB can not be defined\n", yylineno, digit + 10);
             }
             else if(digit >= 10) {
               hasError = 1;
               printf("%d: %dF can not be defined\n", yylineno, digit - 10);
             }
             else {
               list = localSymbolPatches[digit];
               localSymbolPatches[digit] = NULL;
             }
           }
           else if(T_count(globalSymbolMap, $1.global)) {
             hasError = 1;
             printf("%d: %s can not be defined more than once\n", yylineno, S_name($1.global));
           }
           else {
             list = T_look(globalSymbolPatches, $1.global);
             T_insert(globalSymbolPatches, $1.global, NULL);
           }
           // handle all the literall constants and rest undefind symbols
           epilog();
           // handle the end symbol
           handleEndSymbol(list);
         }
       | endInst1 {epilog();}
       ;

normalInstList: normalInstList normalInst
              | normalInst
              ;

